use std::cmp::Ordering;
use std::ptr;

mod alloc_testing {
    // Implementations for alloc_test_* functions
}

mod framework {
    // Implementations for test framework functions
}

mod compare_int {
    pub fn int_equal(a: i32, b: i32) -> bool {
        a == b
    }

    pub fn int_compare(a: i32, b: i32) -> Ordering {
        a.cmp(&b)
    }
}

mod sorted_array {
    use std::cmp::Ordering;
    use std::ptr;

    pub type SortedArrayValue = *const i32;

    pub struct SortedArray {
        data: Vec<SortedArrayValue>,
        equal_fn: fn(SortedArrayValue, SortedArrayValue) -> bool,
        compare_fn: fn(SortedArrayValue, SortedArrayValue) -> Ordering,
    }

    impl SortedArray {
        pub fn new(
            equal_fn: fn(SortedArrayValue, SortedArrayValue) -> bool,
            compare_fn: fn(SortedArrayValue, SortedArrayValue) -> Ordering,
        ) -> Self {
            SortedArray {
                data: Vec::new(),
                equal_fn,
                compare_fn,
            }
        }

        pub fn insert(&mut self, value: i32) {
            let ptr = Box::into_raw(Box::new(value));
            let pos = self.data.binary_search_by(|&x| (self.compare_fn)(ptr, x)).unwrap_or_else(|e| e);
            self.data.insert(pos, ptr);
        }

        pub fn remove(&mut self, index: usize) {
            if index < self.data.len() {
                unsafe { Box::from_raw(self.data.remove(index)) };
            }
        }

        pub fn remove_range(&mut self, start: usize, length: usize) {
            for i in (start..start + length).rev() {
                if i < self.data.len() {
                    unsafe { Box::from_raw(self.data.remove(i)) };
                }
            }
        }

        pub fn index_of(&self, value: SortedArrayValue) -> Option<usize> {
            self.data.iter().position(|&x| (self.equal_fn)(value, x))
        }

        pub fn get(&self, index: usize) -> Option<SortedArrayValue> {
            self.data.get(index).copied()
        }

        pub fn len(&self) -> usize {
            self.data.len()
        }
    }

    impl Drop for SortedArray {
        fn drop(&mut self) {
            for &ptr in &self.data {
                unsafe { Box::from_raw(ptr as *mut i32) };
            }
        }
    }
}

use sorted_array::{SortedArray, SortedArrayValue};

fn check_sorted_prop(sortedarray: &SortedArray) {
    for i in 0..sortedarray.len() - 1 {
        assert!((compare_int::int_compare)(sortedarray.get(i).unwrap(), sortedarray.get(i + 1).unwrap()) != Ordering::Greater);
    }
}

fn free_sorted_ints(sortedarray: &mut SortedArray) {
    // The SortedArray's Drop implementation will handle freeing the memory
}

fn test_sortedarray_new_free() {
    let mut sortedarray = SortedArray::new(compare_int::int_equal, compare_int::int_compare);
    assert!(!sortedarray.data.is_empty());
    drop(sortedarray);

    // Freeing null is not applicable in Rust as it doesn't have null pointers

    alloc_testing::alloc_test_set_limit(0);
    let sortedarray = SortedArray::new(compare_int::int_equal, compare_int::int_compare);
    assert!(sortedarray.data.is_empty());

    alloc_testing::alloc_test_set_limit(-1);
}

fn test_sortedarray_insert() {
    let mut sortedarray = SortedArray::new(compare_int::int_equal, compare_int::int_compare);

    for _ in 0..20 {
        let i = (rand::random::<f32>() * 100.0) as i32;
        sortedarray.insert(i);
    }

    check_sorted_prop(&sortedarray);
    free_sorted_ints(&mut sortedarray);
}

fn test_sortedarray_remove() {
    let mut sortedarray = SortedArray::new(compare_int::int_equal, compare_int::int_compare);

    if let Some(ip) = sortedarray.get(TEST_REMOVE_EL + 1) {
        let i = unsafe { *ip };
        free_sorted_ints(&mut sortedarray);
        sortedarray.remove(TEST_REMOVE_EL);
        assert_eq!(unsafe { *sortedarray.get(TEST_REMOVE_EL).unwrap() }, i);
    }

    check_sorted_prop(&sortedarray);
    free_sorted_ints(&mut sortedarray);
}

fn test_sortedarray_remove_range() {
    let mut sortedarray = SortedArray::new(compare_int::int_equal, compare_int::int_compare);

    let new: Vec<i32> = (0..TEST_REMOVE_RANGE_LENGTH)
        .map(|i| unsafe { *sortedarray.get(TEST_REMOVE_RANGE + TEST_REMOVE_RANGE_LENGTH + i).unwrap() })
        .collect();

    for i in 0..TEST_REMOVE_RANGE_LENGTH {
        free_sorted_ints(&mut sortedarray);
    }

    sortedarray.remove_range(TEST_REMOVE_RANGE, TEST_REMOVE_RANGE_LENGTH);

    check_sorted_prop(&sortedarray);
    free_sorted_ints(&mut sortedarray);
}

fn test_sortedarray_index_of() {
    let mut sortedarray = SortedArray::new(compare_int::int_equal, compare_int::int_compare);
    sortedarray.insert(42);

    assert_eq!(sortedarray.index_of(sortedarray.get(0).unwrap()), Some(0));
    free_sorted_ints(&mut sortedarray);
}

fn test_sortedarray_get() {
    let mut sortedarray = SortedArray::new(compare_int::int_equal, compare_int::int_compare);
    sortedarray.insert(42);

    assert_eq!(unsafe { *sortedarray.get(0).unwrap() }, 42);
    free_sorted_ints(&mut sortedarray);
}

const TEST_REMOVE_EL: usize = 5;
const TEST_REMOVE_RANGE_LENGTH: usize = 3;

fn main() {
    test_sortedarray_new_free();
    test_sortedarray_insert();
    test_sortedarray_remove();
    test_sortedarray_remove_range();
    test_sortedarray_index_of();
    test_sortedarray_get();
}
